package main

import (
	"fmt"
	"sort"
)

// 合并区间：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
// 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
// 可以先对区间数组按照区间的起始位置进行排序，然后使用一个切片来存储合并后的区间，遍历排序后的区间数组，
// 将当前区间与切片中最后一个区间进行比较，如果有重叠，则合并区间；如果没有重叠，则将当前区间添加到切片中

func merge(intervals [][]int) [][]int {
	// 边界条件：空区间数组直接返回空
	if len(intervals) == 0 {
		return [][]int{}
	}

	// 第一步：按区间的起始位置升序小的在前（>就是降序，大的在前）
	// 排序后，重叠的区间会相邻，便于后续合并
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	// 第二步：初始化合并后的区间切片，先放入第一个区间
	merged := [][]int{intervals[0]}

	// 第三步：遍历剩余区间，逐个判断是否需要合并
	for i := 1; i < len(intervals); i++ {
		// 当前遍历的区间
		current := intervals[i]
		// 合并切片中最后一个已合并的区间（待比较的前一个区间）
		lastMerged := merged[len(merged)-1]

		// 判断是否重叠：前一个区间的end >= 当前区间的start，说明有重叠
		if lastMerged[1] >= current[0] {
			// 合并区间：start取前一个的start，end取两者end的最大值
			merged[len(merged)-1][1] = max(lastMerged[1], current[1])
		} else {
			// 无重叠，直接将当前区间加入合并切片
			merged = append(merged, current)
		}
	}

	return merged
}

// 返回两个整数中的最大值
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	// 有重叠区间-取重叠区间前后值
	intervals1 := [][]int{{1, 3}, {8, 10}, {2, 6}, {15, 18}}
	fmt.Println(merge(intervals1)) // 输出：[[1 6] [8 10] [15 18]]

	// 完全包含的区间
	intervals2 := [][]int{{1, 4}, {2, 3}}
	fmt.Println(merge(intervals2)) // 输出：[[1 4]]

	// 无重叠区间
	intervals3 := [][]int{{1, 2}, {3, 4}, {5, 6}}
	fmt.Println(merge(intervals3)) // 输出：[[1 2] [3 4] [5 6]]

	// 单个区间
	intervals4 := [][]int{{5, 5}}
	fmt.Println(merge(intervals4)) // 输出：[[5 5]]
}
